//归并排序
class Solution {
public:
    vector<int> tmp;
    void MergeSort(vector<int> &nums, int left , int right)
    {
        if(left >= right) return;
        int mid = left + (right-left)/2;
        MergeSort(nums,left,mid);
        MergeSort(nums,mid+1,right);

        //合并两个有序数组
        int cur1 = left , cur2 = mid+1 , i = 0;
        while(cur1 <= mid && cur2 <= right)
            tmp[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
        while(cur1 <= mid)
            tmp[i++] = nums[cur1++];
        while(cur2 <= right)
            tmp[i++] = nums[cur2++];

        //还原
        for(int i = left ; i <= right ; ++i)
            nums[i] = tmp[i-left];
    }
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        tmp.resize(n);
        MergeSort(nums,0,n-1);
        return nums;
    }
};

//交易逆序对的总数
class Solution {
public:
    vector<int> tmp;
    void MergeSort(vector<int>& nums,int left,int right,int &ret)
    {
        if(left >= right) return;
        int mid = left + (right - left)/2;
        MergeSort(nums,left,mid,ret);
        MergeSort(nums,mid+1,right,ret);

        int cur1 = left , cur2 = mid+1 , i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
            {
                tmp[i++] = nums[cur1++];
            }
            else 
            {
                ret += (mid - cur1 + 1);
                tmp[i++] = nums[cur2++];
            }
        }
        while(cur1 <= mid)
            tmp[i++] = nums[cur1++];
        while(cur2 <= right)
            tmp[i++] = nums[cur2++];

        for(int i = left ; i <= right ; ++i)
        {
            nums[i] = tmp[i-left];
        }
    }
    int reversePairs(vector<int>& record) {
        int n = record.size();
        tmp.resize(n);
        int ret = 0;
        MergeSort(record,0,n-1,ret);
        return ret;
    }
};

//计算右侧小于当前元素的个数
class Solution {
public:
    vector<int> temp1;
    vector<int> temp2;
    vector<int> index;
    void MergeSort(vector<int>& nums , int left , int right , vector<int>& ret)
    {
        if(left >= right) return;
        int mid = left + (right - left)/2;
        MergeSort(nums,left,mid,ret);
        MergeSort(nums,mid+1,right,ret);

        int cur1 = left , cur2 = mid+1 , i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
            {
                temp1[i] = nums[cur2];
                temp2[i] = index[cur2++];
            }
            else 
            {
                int size = right-cur2+1;
                ret[index[cur1]] += size;
                temp1[i] = nums[cur1];
                temp2[i] = index[cur1++];
            }
            i++;
        }
        while(cur1 <= mid)
        {
            temp1[i] = nums[cur1];
            temp2[i++] = index[cur1++];
        }
        while(cur2 <= right)
        {
            temp1[i] = nums[cur2];
            temp2[i++] = index[cur2++];
        }
        for(int i = left ; i <= right ; ++i)
        {
            nums[i] = temp1[i-left];
            index[i] = temp2[i-left];
        }
    }
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        temp1.resize(n);
        temp2.resize(n);
        for(size_t i = 0 ; i < n ; ++i)
        {
            index.push_back(i);
        }
        //index表示的是元素的原始下标
        vector<int> ret(n);
        MergeSort(nums,0,n-1,ret);

        return ret;
    }
};















